import collections
from cmath import inf
from typing import List


def dijkstra(n: int, graph: List[int]) -> List[int]:
    visit = [False] * n
    dist = [inf] * n
    dist[0] = 0

    for i in range(n):
        min_dist = inf
        middle = 0
        for j in range(n):
            if not visit[j] and min_dist > dist[j]:
                min_dist = dist[j]
                middle = j
        for j in range(n):
            if not visit[j] and graph[middle][j] + min_dist < dist[j]:
                dist[j] = graph[middle][j] + min_dist
        visit[middle] = True

    return dist


class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append((b, 1))
            graph[b].append((a, 1))

        queue = collections.deque([(0, 0)])
        dist = [float('inf')] * n
        dist[0] = 0

        while queue:
            curr, dis = queue.popleft()
            if dist[curr] < dis:
                continue
            for next, t in graph[curr]:
                if dist[next] > dis + t:
                    dist[next] = dis + t
                    queue.append((next, dis + t))

        ans = 0
        for i in range(1, n):
            if patience[i] >= 2 * dist[i]:
                ans = max(ans, 2 * dist[i])
            else:
                if 2 * dist[i] % patience[i] == 0:
                    gone = patience[i]
                else:
                    gone = 2 * dist[i] % patience[i]
                ans = max(ans, 4 * dist[i] - gone)
        return ans + 1


a = [[0, 1, inf, inf, inf], [1, 0, 1, inf, inf], [inf, 1, 0, 1, inf], [inf, inf, 1, 0, 1], [inf, inf, inf, 1, 0]]
print(dijkstra(5, a))
